﻿#ifndef __SS_HEAP_H__
#define __SS_HEAP_H__
#include "ssArray.h"
#include "ssNumArray.h"

namespace StarSeeker
{

template<typename T, typename A>
class ssHeapBase
{
public:
	ssHeapBase()
	{
		m_min = true;
	}
	ssHeapBase(bool min)
	{
		m_min = min;
	}
	ssHeapBase(bool min, T *pArr, ulint count)
	{
		m_min = min;
		m_arr.CopyFrom(pArr, count);
		InitHeap();
	}
	ssHeapBase(const ssHeapBase& h)
		:m_arr(h.m_arr)
	{
		m_min = h.min;
	}
	virtual ~ssHeapBase()
	{
	}

	//入堆
	bool Push(T& val)
	{
		if (m_arr.IsFull())
		{
			if (!m_arr.Resize(m_arr.MaxCount() * 4))
			{
				return false;
			}
		}
		if (m_arr.Count()==0)
		{
			return m_arr.PushBack(val);
		}
		else
		{
			Up(m_arr.Count(), val);
			m_arr.SetCount(m_arr.Count() + 1);
		}
		return true;
	}
	//出堆
	bool Pop()
	{
		if (m_arr.Count()==1)
		{
			m_arr.SetCount(0);
			return true;
		}
		else if (m_arr.Count()>1)
		{
			m_arr[0] = m_arr[m_arr.Count()-1];
			Down(0);
			m_arr.SetCount(m_arr.Count()-1);
			return true;
		}
		return false;
	}
	//堆顶元素
	T& Top()
	{
		return m_arr[0];
	}
	//数量
	ulint Count() const
	{
		return m_arr.Count();
	}
	//存数据的数组
	const A& Array()
	{
		return m_arr;
	}

	//检查堆完整性
	bool CheckHeap()
	{
		for (ulint i = 1; i < m_arr.Count(); ++i)
		{
			ulint p = (i - 1) / 2;
			if (m_min)
			{
				if (m_arr[p] > m_arr[i])
				{
					return false;
				}
			}
			else
			{
				if (m_arr[p] < m_arr[i])
				{
					return false;
				}
			}
		}
		return true;
	}

private:
	void Up(ulint offset, T& newVal)
	{
		lint parent = (offset - 1) / 2;
		while (parent >= 0 && offset>0)
		{
			if (m_min)
			{
				if (m_arr[parent] <= newVal)
					break;
			}
			else
			{
				if (m_arr[parent] >= newVal)
					break;
			}
			{
				m_arr[offset] = m_arr[parent];
				offset = parent;
				parent = (offset - 1) / 2;
			}
		}
		m_arr[offset] = newVal;
	}
	void Down(ulint offset)
	{
		ulint n = m_arr.Count();
		ulint child = 2 * offset + 1;
		T tmp = m_arr[offset];
		while (child < n)
		{
			if (child + 1 < n)//找最大或最小子节点
			{
				if (m_min)
				{
					if (m_arr[child] > m_arr[child + 1])
						child++;
				}
				else
				{
					if (m_arr[child] < m_arr[child + 1])
						child++;
				}
			}
			if (m_min)
			{
				if (m_arr[child] >= tmp)
					break;
			}
			else
			{
				if (m_arr[child] <= tmp)
					break;
			}
			{
				m_arr[offset] = m_arr[child];
				offset = child;
				child = 2 * offset + 1;
			}
		}
		m_arr[offset] = tmp;
	}
	//初始建堆 
	void InitHeap()
	{
		for (ulint i = m_arr.Count() / 2 - 1; i >= 0; i--)
		{
			Down(i);
			if (i==0)
			{
				break;
			}
		}
	}

private:
	A			m_arr;
	bool		m_min;//true最小堆，false最大堆
};

template <typename T, ulint NUM = 0>
class ssHeap : public ssHeapBase<T, ssArray<T, NUM> >
{
public:
	ssHeap(bool min) :ssHeapBase<T, ssArray<T, NUM> >(min) {}
	ssHeap(bool min, T *pArr, ulint count) :ssHeapBase<T, ssArray<T, NUM> >(min, pArr, count) {}
	ssHeap(const ssHeap& h) :ssHeapBase<T, ssArray<T, NUM> >(h) {}
};

template <typename T, ulint NUM = 0>
class ssNumHeap : public ssHeapBase<T, ssNumArray<T, NUM> >
{
public:
	ssNumHeap(bool min) :ssHeapBase<T, ssNumArray<T, NUM> >(min) {}
	ssNumHeap(bool min, T *pArr, ulint count) :ssHeapBase<T, ssNumArray<T, NUM> >(min, pArr, count) {}
	ssNumHeap(const ssNumHeap& h) :ssHeapBase<T, ssNumArray<T, NUM> >(h) {}
};

}
#endif
